#include "stack_queue.h"
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<cstring>
#include<vector>
#include<sstream>
using namespace std;

MyStack::MyStack()
{
    topNode=NULL;
    stackSize = 0;
}

MyStack::~MyStack()
{
    while (topNode != NULL) {
        listNode* q = topNode;
        topNode = topNode->next;
        delete q;
   } 
}

bool MyStack::push(const int& item)
{
        listNode* p = new listNode;
        if (p == NULL)return 0;
        p->data = item;
        p->next = topNode;
        topNode = p;
        stackSize++;
        return 1;
}
bool MyStack::pop(int&item)
{
    
    if (!topNode)
        return false;
    else {
        item = topNode->data;
        listNode* p = topNode;
        topNode = topNode->next;
        delete p;
        stackSize--;
        return true;
    }
   
}
bool MyStack::getTop(int&item)
{
    if (topNode == NULL)return 0;
    else {
        item = topNode->data;
        return 1;
    }
}
bool MyStack::pop(char& item)
{

    if (!topNode)
        return false;
    else {
        item = topNode->data;
        listNode* p = topNode;
        topNode = topNode->next;
        delete p;
        stackSize--;
        return true;
    }

}
bool MyStack::getTop(char& item)
{
    if (topNode == NULL)return 0;
    else {
        item = topNode->data;
        return 1;
    }
}
void MyStack::printStack(){
    listNode* p = topNode;

    while(p != NULL){
        if(p->next == NULL)
            cout << p->data << endl;
        else
            cout << p->data << ",";

        p = p->next;
        
    }
}
//创建队列,容量为capacity
MyQueue::MyQueue(const int &s)
{
    first=cnt=last=new listNode;
    capacity=s-1;
};
//销毁队列
MyQueue::~MyQueue(){};
//入队,成功返回true,失败返回false
bool MyQueue::enQueue(const int &num)
{
    if(size==capacity)return false;
    last->next=new listNode;
    last->next->before=last;
    last=last->next;
    last->data=num;
    size++;
    return true;
}
//出栈,成功返回true,失败返回false, 出队元素放在item
bool MyQueue::deQueue(int &item)
{
    if(first->next==NULL)return false;
    size--;
    listNode *p=first->next;
    item=p->data;
    first->next=p->next;
    if(first->next!=NULL)first->next->before=first;
    delete p;
    return true;
}
//返回队头元素
bool MyQueue::getFront(int &item)
{
    if(first==last)return false;
    item=first->next->data;
    return true;
}
bool MyQueue::isFull()
{
    return size==capacity;
}
//按照队头到队尾的顺序输出栈内所有元素

bool MyStack::push(const char& item)
{
    listNode* p = new listNode;
    if (p == NULL)return 0;
    p->data = item;
    p->next = topNode;
    topNode = p;
    stackSize++;
    return 1;
}
void MyQueue::printQueue()
{
    listNode *p=first->next;
    for(;p!=last;p=p->next)
    {
        cout<<p->data<<",";
    }
    cout<<last->data<<endl;
    return;
}
int youxian(const char& op)
{
    switch (op)
    {
      case '#':return 0;break;
      case '+':return 1;break;
      case '-':return 1;break;
      case '*':return 2;break;
      case '/':return 2;break;
    }
    return 0;
}
bool postfixExpression(const string&str, string&result)
{
    result = "";
    char item;
    MyStack opp;
   
    for (int i = 0; i < str.length(); i++) {
        if (str[i] == '(')opp.push(str[i]);
        else if (str[i] == ')') {
            if (opp.stackSize == 0)
            {
                result = "Expression is wrong!"; return 0;
            }
            else opp.pop(item);
        }
    }
    if (opp.stackSize != 0) {
        result = "Expression is wrong!";
        return 0;
    }
    opp.push('#');
   
    for (int i = 0; i < str.length(); i++) {
        if (str[i] <= '9' && str[i] >= '1') {
            result += str[i];
        }
        else {
            opp.getTop(item);
            if ((str[i] == '(' || item == '(') && str[i] != ')')opp.push(str[i]);
            else{
                if (str[i] != ')' && youxian(str[i]) > youxian(item))opp.push(str[i]);
                else if (str[i] != ')' && youxian(str[i]) <= youxian(item))
                {
                    opp.pop(item);
                    result += item;
                   i--;
                }
                else if (str[i] == ')') {
                    while (item != '(') {
                        opp.pop(item);
                        result += item;
                        opp.getTop(item);
                    }
                    opp.pop(item);
                    opp.getTop(item);
                }
            }
        }
    }
    while (opp.stackSize != 1) {
        opp.pop(item);
        result += item;
    }
    opp.pop(item);
    int cop=0, cnum=0;
    for (int i = 0; i < result.length(); i++) {
        if (result[i] <= '9' && result[i] >= '1') { cnum++; }
        else
            cop++;
    }
    if (cop != cnum-1)
    {
        result = "Expression is wrong!"; return 0;
    }
    return 1;
}
int cal(char OP, int num1, int num2) {
    if (OP == '+') { return(num1 + num2); }
    if (OP == '-') { return (num1 - num2); }
    if (OP == '*') { return (num1 * num2); }
    if (OP == '/') { return (num1 / num2); }
}
bool expressionVal(const string&str, int&result)
{
    MyStack op, num;
    result = 0;
    string res;
    int num1, num2;
    postfixExpression(str, res);
    if (res == "Expression is wrong!") { result = 0; return 0; }
    for (int i = 0; i < res.length(); i++) {
        if (res[i] <= '9' && res[i] >= '1') {
            num.push(res[i]-'0');
        }
        else {
            num.pop(num2); num.pop(num1);
            num1 = cal(res[i], num1, num2);
            num.push(num1);
        }
    }
    num.pop(result);
    return 1;
}
void yanghui(const int &n)
{
    MyQueue q(1000000);
    q.enQueue(0);
    q.enQueue(1);
    int is=-1;
    for(int i=1,u,t;is<=n;i++)
    {
        q.deQueue(u);
        if(u==0)
        {
            q.enQueue(0);
            is++;
            if(is!=0&&is!=1)cout<<endl;
        }
        q.getFront(t);
        if(u!=0&&is!=0){cout<<u;
        if(t!=0)cout<<",";}
        q.enQueue(u+t);
    }
}
